package com.zj.leetcode.medium.greed;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: algorithm
 * @description: Dota2 参议院
 * 649 dota2-senate
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class Dota2Senate {
    public static void main(String[] args) {
        String senate = "RD";
        Solution solution = new Dota2Senate().new Solution();
        System.out.println(solution.predictPartyVictory(senate));
        System.out.println(624 / 3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String predictPartyVictory(String senate) {
            Queue<Integer> radiant = new LinkedList<>();
            Queue<Integer> dire = new LinkedList<>();
            int n = senate.length();
            char c;
            for (int i = 0; i < n; i++) {
                c = senate.charAt(i);
                if (c == 'R') {
                    radiant.offer(i);
                } else {
                    dire.offer(i);
                }
            }
            while (!radiant.isEmpty() && !dire.isEmpty()) {
                int r = radiant.remove();
                int d = dire.remove();
                if (r < d) {
                    radiant.offer(r + n);
                } else {
                    dire.offer(d + n);
                }
            }
            return radiant.isEmpty() ? "Dire" : "Radiant";
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
